1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include <cstdio>
#include <queue>
#define LL long long
const int maxn = 2e5 + 5;
using namespace std;
int f[maxn];
int getf(int x){return x == f[x] ? x : f[x] = getf(f[x]);}
struct A{
int a, b, id;
bool operator<(A x)const{
return 1ll * b * x.a > 1ll * a * x.b;
}
bool operator!=(A x)const{
return a != x.a || b != x.b;
}
}a[maxn]; LL ans = 0;
priority_queue <A> q;
int n, anc[maxn];
int main(){
scanf("%d", &n);
for (int i = 2; i <= n; i++) scanf("%d", anc + i);
for (int val, i = 1; i <= n; i++){
scanf("%d", &val);
f[i] = i;
if (val == 0) a[i] = (A){1, 0, i};
else a[i] = (A){0, 1, i};
if (i != 1) q.push(a[i]);
}
while (!q.empty()){
A t = q.top(); q.pop();
int cur = getf(t.id);
if (a[cur] != t) continue;
int fa = getf(anc[cur]);
ans += 1ll * a[fa].b * a[cur].a;
a[fa].a += a[cur].a;
a[fa].b += a[cur].b;
f[getf(cur)] = f[getf(fa)];
if (fa != 1) q.push(a[fa]);
}
printf("%lld\n", ans);
return 0;
}
|